Năm 1999, Yudhoyono được bổ nhiệm làm Bộ trưởng Bộ Tài nguyên Mỏ và Năng lượng trong Chính phủ của Tổng thống Abdurrahman Wahid.

Tháng 8 năm 2000, Yudhoyono làm Bộ trưởng Bộ An ninh và Chính trị. Do cải tổ nội các, nhiệm vụ chính của Yudhoyono là tách rời quân đội khỏi hệ thống chính trị. Một nhiệm vụ khác nữa, Tổng thống Abdurrahman Wahid giao cho Yudhoyono làm cầu nối giữa Wahid và gia đình Suharto.

Năm 2001, với áp lực chính trị ngày càng tăng, Wahid chỉ định Yudhoyono thành lập và làm Chủ tịch trung tâm giải quyết khủng hoảng. Khi Wahid đối mặt với việc bị buộc tội phản quốc, Yudhoyono đã từ bỏ chức vụ này; sau đó ông bị Tổng thống Abdurrahman Wahid sa thải.

Ngày 23 tháng 7 năm 2001, Hội nghị Hiệp thương Nhân dân MPR họp phiên đặc biệt đã buộc tội Abdurrahman Wahid và bổ nhiệm bà Megawati Sukarnoputri làm Tổng thống Indonesia. Tại cuộc bỏ phiếu của MPR, Yudhoyono đã tham gia tranh cử với Akbar Tajung của Đảng Golkar và Hamzah Haz của Đảng Thống nhất Phát triển PPP. Yudhoyono thất bại và Hamzah trở thành Phó Tổng thống. Ông Yudhoyono được tái bổ nhiệm chức Bộ trưởng Bộ An ninh và Chính trị trong Nội các của Tổng thống Megawati.